#include <bits/stdc++.h>

using namespace std;

//链表结点
struct ListNode
{
    int _address;
    int _val;
    int _nextAddr;
    ListNode(int val, int address, int nextAddr)
        : _val(val), _address(address), _nextAddr(nextAddr)
    {
    }
    ListNode(int address)
        : _val(0), _address(address), _nextAddr(-1)
    {
    }
};
//比较器
struct cmp
{
    bool operator()(ListNode *node1, ListNode *node2)
    {
        if (abs(node1->_val) < abs(node2->_val))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

void dedupNode(unordered_map<int, ListNode *> hashMap, ListNode *head,
               set<ListNode *, cmp> &dup, vector<ListNode *> &dupList, vector<ListNode *> &delList)
{
    ListNode *cur = hashMap[head->_address];
    while (cur && cur->_address != -1)
    {
        auto ret = dup.insert(cur);
        if (ret.second)
        {
            dupList.emplace_back(cur);
        }
        else
        {
            delList.emplace_back(cur);
        }
        cur = hashMap[cur->_nextAddr];
    }
    //更新连接顺序
    for (int i = 0; i < (int)dupList.size(); i++)
    {
        if (i == (int)dupList.size() - 1)
        {
            dupList[i]->_nextAddr = -1;
        }
        else
        {
            dupList[i]->_nextAddr = dupList[i + 1]->_address;
        }
    }
    for (int i = 0; i < (int)delList.size(); i++)
    {
        if (i == (int)delList.size() - 1)
        {
            delList[i]->_nextAddr = -1;
        }
        else
        {
            delList[i]->_nextAddr = delList[i + 1]->_address;
        }
    }
}
int main()
{
    //第一个结点的地址
    int address = -1;
    //该链表一共有N个结点
    int N = 0;
    cin >> address >> N;
    //构建链表(单向无头不循环链表)
    ListNode *head = new ListNode(address);
    //"地址"与结点的映射关系表
    unordered_map<int, ListNode *> hashMap;
    //预留空间
    hashMap.rehash(N);
    //循环建立链表结点(同时建立地址与结点的映射关系)
    int count = N;
    while (count--)
    {
        int val = 0;
        int newAddress = -1;
        cin >> address >> val >> newAddress;
        ListNode *newNode = new ListNode(val, address, newAddress);
        hashMap[address] = move(newNode);
    }
    //进行去重
    set<ListNode *, cmp> dup;
    //接收去重结果
    vector<ListNode *> dupList, delList;
    dedupNode(hashMap, head, dup, dupList, delList);
    //输出
    for (const auto &val : dupList)
    {
        if (val->_nextAddr != -1)
        {
            printf("%05d %d %05d\n", val->_address, val->_val, val->_nextAddr);
        }
        else
        {
            printf("%05d %d %d\n", val->_address, val->_val, val->_nextAddr);
        }
    }
    for (const auto &val : delList)
    {
        if (val->_nextAddr != -1)
        {
            printf("%05d %d %05d\n", val->_address, val->_val, val->_nextAddr);
        }
        else
        {
            printf("%05d %d %d\n", val->_address, val->_val, val->_nextAddr);
        }
    }
    return 0;
}
